10559. Подсчет стогов сена

 

Фермер Джон разместил свои n стогов сена в различных точках одномерной дороги вдоль своей фермы. Вам необходимо ответить на q запросов о том, сколько стогов сена находится в указанном участке дороги.

 

Вход. Первая строка содержит два целых числа n (1 ≤ n ≤ 105) и q (1 ≤ q ≤ 105). Следующая строка содержит n различных целых чисел, каждое из которых находится в интервале 0 ... 109, обозначающих местоположения стогов сена.

Каждая из следующих q строк содержит два целых числа a и b (0 ≤ a ≤ b ≤ 109), задающих запрос на количество стогов сена между a и b, включительно.

 

Выход. Выведите q строк. Для каждого запроса выведите в отдельной строке количество стогов сена в соответствующем интервале.

 

Пример входа

Пример выхода

4 6

3 2 7 5

2 3

2 4

2 5

2 7

4 6

8 10

2

2

3

4

1

0

 

 

 

РЕШЕНИЕ

бинарный поиск

 

Анализ алгоритма

Отсортируем координаты стогов сена.

Пусть f(x) – количество стогов сена в интервале [0; x]. Тогда количество стогов сена в интервале [a; b] будет равно f(b) – f(a – 1).

Значение f(x) находим с помощью бинарного поиска.

 

Реализация алгоритма

Читаем входные данные.

 

scanf("%d %d", &n, &q);

v.resize(n);

for (i = 0; i < n; i++)

  scanf("%d", &v[i]);

 

Сортируем координаты стогов сена.

 

sort(v.begin(), v.end());

 

Обрабатываем q запросов.

 

for (i = 0; i < q; i++)

{

 

Находим и выводим количество стогов сена res в интервале от a до b включительно.

 

  scanf("%d %d", &a, &b);

  res = upper_bound(v.begin(), v.end(), b) –

        upper_bound(v.begin(), v.end(), a - 1);

  printf("%d\n", res);

}

 

Python реализация

 

import bisect

 

Читаем входные данные.

 

n, q = map(int, input().split())

v = list(map(int, input().split()))

 

Сортируем координаты стогов сена.

 

v.sort()

 

Обрабатываем q запросов.

 

for _ in range(q):

 

Находим и выводим количество стогов сена res в интервале от a до b включительно.

 

  a, b = map(int, input().split())

  res = bisect.bisect_right(v, b) - bisect.bisect_right(v, a - 1)

  print(res)